package com.dycong.common.dataStructuresAndAlgorithms;

// BinarySearchTree class
//
// CONSTRUCTION: with no initializer
//
// ******************PUBLIC OPERATIONS*********************
// void insert( x )       --> Insert x
// void remove( x )       --> Remove x
// Comparable find( x )   --> Return item that matches x
// Comparable findMin( )  --> Return smallest item
// Comparable findMax( )  --> Return largest item
// boolean isEmpty( )     --> Return true if empty; else false
// void makeEmpty( )      --> Remove all items
// void printTree( )      --> Print tree in sorted order



/**
 * Implements an unbalanced binary search tree.
 * Note that all "matching" is based on the compareTo method.
 *
 * @author Mark Allen Weiss
 */
public class BinarySearchTree {
    /**
     * Construct the tree.
     */
    public BinarySearchTree() {
        root = null;
    }

    /**
     * @param x
     * @param t
     * @return
     * @see 尾递归在递归方法最后 （例如return）自进行function（）调用，接下来就是虚拟机行为http://www.cnblogs.com/bellkosmos/p/5280619.html
     * @see java尚未对尾递归做优化，尽量使用while()，for()代替递归
     */
    private boolean contains(Comparable x, BinaryNode t) {
        if (t == null)
            return false;
        int compareResult = x.compareTo(t.element);
        if (compareResult < 0)
            return contains(x, t.left);
        else if (compareResult > 0)
            return contains(x, t.right);
        else
            return true;  //match,可能性最小的放在最后
    }


    public void test01() {
        BinarySearchTree t = new BinarySearchTree();
        final int NUMS = 4000;
        final int GAP = 37;
        for (int i = GAP; i != 0; i = (i + GAP) % NUMS)
            t.insert(new Integer(i));
        for (int search = 0; search < 40000; search++) {
            if (contains(search, t.root) != contain(search, t.root))
                System.out.println("ERROR");
        }
        System.out.println("OK");
    }

    /**
     * @param x
     * @param t
     * @return
     * @see 改造递归-->while();
     */
    private boolean contain(Comparable x, BinaryNode t) {
        if (t == null)
            return false;
        int compareResult = x.compareTo(t.element);
        while ((null != t.right & compareResult > 0) || (null != t.left & compareResult < 0)) {
            while (compareResult < 0) {
                if (null != t.left) {
                    t = t.left;
                    compareResult = x.compareTo(t.element);
                }
                break;
            }
            while (compareResult > 0) {
                if (null != t.right) {
                    t = t.right;
                    compareResult = x.compareTo(t.element);
                }
                break;
            }
        }

        if (compareResult == 0) {
            return true;
        }
        return false;
    }

    /**
     * Insert into the tree; duplicates are ignored.
     *
     * @param x the item to insert.
     */
    public void insert(Comparable x) {
        root = insert(x, root);
    }

    /**
     * Remove from the tree. Nothing is done if x is not found.
     *
     * @param x the item to remove.
     */
    public BinaryNode remove(Comparable x) {
        root = remove(x, root);
        return root;
    }

    public BinaryNode myRemove(Comparable x) {
        root = myRemove(x, root);
        return root;
    }

    /**
     * Find the smallest item in the tree.
     *
     * @return smallest item or null if empty.
     */
    public Comparable findMin() {
        return elementAt(findMin(root));
    }

    /**
     * Find the largest item in the tree.
     *
     * @return the largest item of null if empty.
     */
    public Comparable findMax() {
        return elementAt(findMax(root));
    }

    /**
     * Find an item in the tree.
     *
     * @param x the item to search for.
     * @return the matching item or null if not found.
     */
    public Comparable find(Comparable x) {
        return elementAt(find(x, root));
    }

    /**
     * Make the tree logically empty.
     */
    public void makeEmpty() {
        root = null;
    }

    /**
     *
     * @return true if empty, false otherwise.
     */
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * Print the tree contents in sorted order.
     */
    public void printTree() {
        if (isEmpty())
            System.out.println("Empty tree");
        else
            printTree(root);
    }

    /**
     * Internal method to get element field.
     *
     * @param t the node.
     * @return the element field or null if t is null.
     */
    private Comparable elementAt(BinaryNode t) {
        return t == null ? null : t.element;
    }

    /**
     * Internal method to insert into a subtree.
     *
     * @param x the item to insert.
     * @param t the node that roots the tree.
     * @return the new root.
     * @see 递归
     */
    private BinaryNode insert(Comparable x, BinaryNode t) {
/* 1*/
        if (t == null)
/* 2*/ t = new BinaryNode(x, null, null);
/* 3*/
        else if (x.compareTo(t.element) < 0)
/* 4*/ t.left = insert(x, t.left);
/* 5*/
        else if (x.compareTo(t.element) > 0)
/* 6*/ t.right = insert(x, t.right);
/* 7*/
        else
/* 8*/          ;  // Duplicate; do nothing
/* 9*/
        return t;
    }

    /**
     * Internal method to remove from a subtree.
     *
     * @param x the item to remove.
     * @param t the node that roots the tree.
     * @return the new root.
     */
    private BinaryNode remove(Comparable x, BinaryNode t) {
        if (t == null)
            return t;   // Item not found; do nothing
        if (x.compareTo(t.element) < 0)
            t.left = remove(x, t.left);
        else if (x.compareTo(t.element) > 0)
            t.right = remove(x, t.right);
        else if (t.left != null && t.right != null) // Two children，@see 找到元素，但有子节点
        {
            t.element = findMin(t.right).element;//找到右边最小的元素，将其element赋值给t,则t的element值变为移除之后的值，再将值为t.element的原Node remove！！
            t.right = remove(t.element, t.right);
        } else
            t = (t.left != null) ? t.left : t.right;
        return t;
    }

    /**
     * @see 出错了
     * @param x
     * @param t
     * @return
     */
    private BinaryNode myRemove(Comparable x, BinaryNode t) {
        if (t == null)
            return t;   // Item not found; do nothing
        if (x.compareTo(t.element) < 0)
            t.left = remove(x, t.left);
        else if (x.compareTo(t.element) > 0)
            t.right = remove(x, t.right);
        else if (t.left != null && t.right != null) // Two children，@see 找到元素，但有子节点
        {
            t.element = findMin(t.right).element;//找到右边最小的元素，将其element赋值给t,则t的element值变为移除之后的值，再将值为t.element的原Node remove！！
            t.right = removeMin(t.element, t.right);
        } else
            t = (t.left != null) ? t.left : t.right;
        return t;
    }

    private BinaryNode removeMin(Comparable x, BinaryNode t) {
        if (t == null)
            return null;
        else if (t.left == null) {
            BinaryNode removed = t;
            if (null != t.right) {
                removeMin(x, t.right);
            } else {
                t = null;
                return removed;
            }
        }else if (null!=t.left&&null==t.right){

        }
        return removeMin(x, t.left);
    }


    /**
     * Internal method to find the smallest item in a subtree.
     *
     * @param t the node that roots the tree.
     * @return node containing the smallest item.
     */
    private BinaryNode findMin(BinaryNode t) {
        if (t == null)
            return null;
        else if (t.left == null)
            return t;
        return findMin(t.left);
    }

    /**
     * Internal method to find the largest item in a subtree.
     *
     * @param t the node that roots the tree.
     * @return node containing the largest item.
     */
    private BinaryNode findMax(BinaryNode t) {
        if (t != null)
            while (t.right != null)
                t = t.right;

        return t;
    }

    /**
     * Internal method to find an item in a subtree.
     *
     * @param x is item to search for.
     * @param t the node that roots the tree.
     * @return node containing the matched item.
     */
    private BinaryNode find(Comparable x, BinaryNode t) {
        if (t == null)
            return null;
        if (x.compareTo(t.element) < 0)
            return find(x, t.left);
        else if (x.compareTo(t.element) > 0)
            return find(x, t.right);
        else
            return t;    // Match
    }

    /**
     * Internal method to print a subtree in sorted order.
     *
     * @param t the node that roots the tree.
     */
    private void printTree(BinaryNode t) {
        if (t != null) {
            printTree(t.left);
            System.out.println(t.element);
            printTree(t.right);
        }
    }

    /**
     * The tree root.
     */
    private BinaryNode root;


    // TestLinkedList program
    public static void main(String[] args) {
        BinarySearchTree t = new BinarySearchTree();
        BinarySearchTree t1 = new BinarySearchTree();
        final int NUMS = 4000;
        final int GAP = 37;

        System.out.println("Checking... (no more output means success)");
        for (int i = GAP; i != 0; i = (i + GAP) % NUMS) {
            t.insert(new Integer(i));
            t1.insert(new Integer(i));
        }

        for (int i = GAP; i != 0; i = (i + GAP) % NUMS) {
//            if (t.remove(new Integer(i)) != t1.myRemove(new Integer(i))) {
//                System.out.println("ERROR");
                System.out.println(t.myRemove(new Integer(i)).element + "-------" + t1.remove(new Integer(i)).element+ "------" + i);
//            }
        }



        if (NUMS < 40)
            t.printTree();
        if (((Integer) (t.findMin())).intValue() != 2 ||
                ((Integer) (t.findMax())).intValue() != NUMS - 2)
            System.out.println("FindMin or FindMax error!");

        for (int i = 2; i < NUMS; i += 2)
            if (((Integer) (t.find(new Integer(i)))).intValue() != i)
                System.out.println("Find error1!");

        for (int i = 1; i < NUMS; i += 2) {
            if (t.find(new Integer(i)) != null)
                System.out.println("Find error2!");
        }

    }
}
